# ---
# title: 435. Non-overlapping Intervals
# id: problem435
# author: Indigo
# date: 2021-06-21
# difficulty: Medium
# categories: Greedy
# link: <https://leetcode.com/problems/non-overlapping-intervals/description/>
# hidden: true
# ---
# 
# Given a collection of intervals, find the minimum number of intervals you need
# to remove to make the rest of the intervals non-overlapping.
# 
# 
# 
# **Example 1:**
# 
#     
#     
#     Input: [[1,2],[2,3],[3,4],[1,3]]
#     Output: 1
#     Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.
#     
# 
# **Example 2:**
# 
#     
#     
#     Input: [[1,2],[1,2],[1,2]]
#     Output: 2
#     Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.
#     
# 
# **Example 3:**
# 
#     
#     
#     Input: [[1,2],[2,3]]
#     Output: 0
#     Explanation: You don't need to remove any of the intervals since they're already non-overlapping.
#     
# 
# 
# 
# **Note:**
# 
#   1. You may assume the interval's end point is always bigger than its start point.
#   2. Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.
# 
# 
## @lc code=start
using LeetCode

function erase_overlap_intervals(intervals::Vector{Tuple{Int,Int}})
    isempty(intervals) && return 0
    sort!(intervals; by=x -> x[2])
    lst, res = intervals[1][2], -1
    for intv in intervals
        intv[1] < lst ? res += 1 : lst = intv[2]
    end
    return res
end
## @lc code=end
